package Queue.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */

/**
 * 暴力法  时间复杂度为O(n) 不推荐   非常不动脑子的做法，面试时如果这么写，offer直接没
 */
@SuppressWarnings("all")
class MaxQueue1 {

    private Deque<Integer> deque;

    public MaxQueue1() {
        deque = new ArrayDeque<>();
    }

    // 暴力扫描即可 不推荐  如果面试时用暴力，估计直接凉，非常不动脑子的方法
    public int max_value() {
        if(deque.isEmpty()) {return -1;}
        int max = Integer.MIN_VALUE;
        for(Integer x : deque) {
            max = (max < x) ? x : max;
        }
        return max;
    }

    // 从队尾进队
    public void push_back(int value) {
        deque.addLast(value);
    }

    // 从对头出队
    public int pop_front() {
        if(deque.isEmpty()) {
            return -1;
        }
        return deque.removeFirst();
    }
}

/**
 * 采用空间换时间的做法，单独设置一个额外的队列维护当前最大值
 * 额外设置一个单调队列，维护当前队列的最大值在队列的头部，队列的单调性
 * 为：从头到尾部 从小到大
 */
@SuppressWarnings("all")
class MaxQueue2 {

    private Deque<Integer> deque; // 普通队列
    private Deque<Integer> dequeMax; // 维护单调性

    public MaxQueue2() {
        deque = new ArrayDeque<>();
        dequeMax = new ArrayDeque<>();
    }

    public int max_value() {
        if(dequeMax.isEmpty()) {
            return -1;
        }
        return dequeMax.getFirst();
    }

    // 从队尾进队
    public void push_back(int value) {
        deque.addLast(value);
        if(dequeMax.isEmpty()) {
            dequeMax.addFirst(value);
            return;
        }
        if(dequeMax.getLast() >= value) {
            dequeMax.addLast(value);
        } else {
            while(!dequeMax.isEmpty() && dequeMax.getLast() < value) {
                dequeMax.removeLast();
            }
            dequeMax.addLast(value);
        }
    }

    // 从对头出队
    public int pop_front() {
        if(deque.isEmpty()) {
            return -1;
        }
        int temp = deque.removeFirst();
        if(temp == dequeMax.getFirst()) {
            dequeMax.removeFirst();
        }
        return temp;
    }
}




@SuppressWarnings("all")
public class 队列最大值 {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (Integer integer : deque) {
            
        }
    }
}
